home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 288_01 / popt.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-05-23  |  2.0 KB  |  61 lines
  1. /*
  2.         HEADER:         CUG000.02;
  3.         TITLE:          PointOpt;
  4.         DATE:           Mar 89;
  5.         DESCRIPTION:    Point Proximity Tour Improvement Algorithm;
  6.         VERSION:        1.0;
  7.         FILENAME:       POPT.C;
  8.         SEE-ALSO:       TSP.C, NN.C, 2OPT.C, HYBRID.C, 3OPT.C, FN.C,
  9.                         BOOLEAN.H, NODELIST.H, TSP.H,
  10.                         BLDMTX.C, PRTMTX.C, TIME.C;
  11.         AUTHORS:        Kevin E. Knauss;
  12. */
  13.  
  14. #include <nodelist.h>
  15.  
  16. long PointOpt (NumberOfVirteces, Path)
  17.    unsigned NumberOfVirteces;
  18.    NODE *Path;
  19. {
  20.    unsigned ArcCost();
  21.    long CircuitCost;
  22.    int count, BestImprove, EXIST, TEST;
  23.    NODE *First, *Last, *Kth, *Best;
  24.  
  25.    count = 1;
  26.    First = Path;
  27.    do {
  28.       BestImprove = 0;
  29.       Last = First->prior;
  30.       for ( Kth = First; Kth != Last->prior->prior; Kth = Kth->next) {
  31.          EXIST = ArcCost (Last->prior->position, Last->position)
  32.                + ArcCost (Last->position, First->position)
  33.                + ArcCost (Kth->position, Kth->next->position);
  34.          TEST  = ArcCost (Last->prior->position, First->position)
  35.                + ArcCost (Kth->position, Last->position)
  36.                + ArcCost (Last->position, Kth->next->position);
  37.          if ((EXIST - TEST) > BestImprove) {
  38.             BestImprove = EXIST - TEST;
  39.             Best = Kth;
  40.          }
  41.       }
  42.       if (BestImprove == 0) {
  43.          First = First->next;
  44.          count++;
  45.       } else {
  46.          First->prior = Last->prior;
  47.          Last->prior->next = First;
  48.          Last->prior = Best;
  49.          Last->next = Best->next;
  50.          Best->next = Last;
  51.          Last->next->prior = Last;
  52.          count = 1;
  53.       }
  54.    } while (count < NumberOfVirteces);
  55.    Last = First->prior;
  56.    CircuitCost = ArcCost (Last->position, First->position);
  57.    for ( Kth = First; Kth != Last; Kth = Kth->next)
  58.       CircuitCost += ArcCost (Kth->position, Kth->next->position);
  59.    return (CircuitCost);
  60. } /* PointOpt */
  61.